package zuo.test2;

import com.sun.xml.internal.bind.v2.model.core.ID;

import java.util.Arrays;

/**
 * @Author: Forx
 * @Data: 2021/6/13
 * @Desc: Algorithm - zuo.test2
 * @Version: v1.0
 */
public class MainClass {
    public static void main(String[] args) {
//        int[] buff1 = {3,4,1,43,5,23,5,3,5,7,78};
//        System.out.println(findMaxRec(buff1, 0, buff1.length - 1));

//        int[] buff2 = {3,4,1,43,5,23,5,3,5,7,78};
//        mergeSort(buff2,0,buff2.length-1);
//        System.out.println(Arrays.toString(buff2));

//        int[] buff3 = {3,4,1,43,5,23,5,3,5,7,78};
//        System.out.println(minSum(buff3, 0, buff3.length - 1));
//        System.out.println(Arrays.toString(buff3));

        int[] buff4 = {3,4,1,43,5,23,5,3,5,7,78};
        pivot(buff4,6);


    }
    /**
     *
     * master公式
     * T(N) = a*T(N/b) + O(N^d)
     * a是子问题调用的次数
     * b是子问题的规模
     * d是除去调用子问题的时间复杂度
     * 本例中左右分别调用一次,因此a=2
     * 每个子问题的规模是N/2 因此b=2
     * 最后求最大值的时间复杂度为O(1)
     * 因此该算法的master公式是
     * T(N) = 2*T(N/2) + O(1)
     * 再求时间复杂度:
     * 如果logb(a) < d 则时间复杂度是O(N^d)
     * 如果logb(a) > d 则时间复杂度是O(N^logb(a))
     * 如果logb(a) = d 则时间复杂度是O(log(N)*(N^d))
     * 本算法中的时间复杂度是O(N)
     * */
    public static int findMaxRec(int[] in,int L,int R){
        if(L==R)return in[L];
        int mid = L+((R-L)>>1);
        int leftMax = findMaxRec(in,L,mid);
        int rightMax = findMaxRec(in,mid+1,R);
        return Math.max(leftMax,rightMax);
    }

    public static void merge(int[] in,int left,int mid,int right){
        int[] help = new int[right-left+1];
        int hp = 0;
        int p1 = left;
        int p2 = mid+1;
        while (p1 <= mid && p2 <= right){
            if(in[p1] >= in[p2]){
                help[hp] = in[p2];
                p2++;
            }else if(in[p1] < in[p2]){
                help[hp] = in[p1];
                p1++;
            }
            hp++;
        }
        while (p1 <= mid){
            help[hp] = in[p1];
            p1++;
            hp++;
        }
        while (p2 <= right){
            help[hp] = in[p2];
            p2++;
            hp++;
        }
        for (int i = 0; i < help.length; i++) {
            in[left+i] = help[i];
        }

    }
    /**
     * master公式是T(N) = 2*T(N/2) + O(N)
     * 故时间复杂度是 O(N) = O(N*logN)
     * */
    public static void mergeSort(int[] in,int left,int right){
        if(left==right)return;
        int mid = left+((right-left)>>1);
        mergeSort(in,left,mid);
        mergeSort(in,mid+1,right);
        merge(in,left,mid,right);
    }
    /**
     * 归并排序的扩展
     * 小和问题和逆序对问题
     * 小和问题
     * 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组
     * 的小和。求一个数组的小和。
     * 例子：[1,3,4,2,5]1左边比1小的数，没有；3左边比3小的数，1;4左
     * 边比4小的数，1、3;2左边比2小的数，1;5左边比5小的数，1、3、4、
     * 2;所以小和为1+1+3+1+1+3+4+2=16
     * 解法是把左边小于它的个数看做右边大于它的个数,等效成另外一个问题
     * 如 [1,3,4,2,5] 4*1+2*3+1*4+1*2 = 16 时间复杂度是O(NlogN)计算方法同上
     *
     * 逆序对问题在一个数组中，左边的数如果比右边的数大，则折两个数
     * 构成一个逆序对，请打印所有逆序对的数量。
     *
     * 这两个问题是一个问题
     * *
     * */
    public static int merge2(int[] in,int left,int mid,int right){
        int[] help = new int[right-left+1];
        int hp = 0;
        int lp = left;
        int rp = mid+1;
        int res = 0;
        while (lp<=mid && rp <= right){
            res+=in[lp] < in[rp] ? (right-rp+1)*in[lp]:0;//这里通过直接计算索引差来算出右边大于它的数
            help[hp++] = in[lp] < in[rp] ? in[lp++]:in[rp++];//排序,为了上面计算索引差做准备
        }
        while (lp<=mid)help[hp++] = in[lp++];
        while (rp<=right)help[hp++] = in[rp++];
        for (int i = 0; i < help.length; i++) {
            in[left+i] = help[i];
        }
        return res;
    }
    public static int minSum(int[] in,int left,int right){
        if(left==right)return 0;
        int mid = left+((right-left)>>1);
        return minSum(in,left,mid) + minSum(in,mid+1,right) + merge2(in,left,mid,right);
    }
    /**
     * 荷兰国旗问题
     * 问题一
     * 给定一个数组arr,和一个数num,请把小于等于num的数放在数组的左边，大于num的
     * 数放在数组的右边。要求额外空间复杂度0(1),时间复杂度0(N)
     * pivo1 pivo2
     * 问题二（荷兰国旗问题）
     * 给定一个数组arr,和一个数num,请把小于num的数放在数组的左边，等于num的数放
     * 在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度0(1),时间复杂度
     * 0(N)
     * pivo3
     * */
    public static void swap(int[] in,int a,int b){
        in[a]^=in[b];
        in[b]^=in[a];
        in[a]^=in[b];
    }
    public static void pivot(int[] in,int piv){
        int left = 0;
        int right = in.length-1;

        while (left<right){
            while (in[left] <= piv && left<right)left++;
            while (in[right] > piv && left<right)right--;
            swap(in,left++,right--);
        }
    }
    public static void pivot2(int[] in,int piv){
        int left = 0;
        int index = 0;
        while (index < in.length){
            if(in[index] <= piv){
                swap(in,left+1,index);
                left++;
                index++;
            }else {
                index++;
            }
        }
    }
    public static void pivo3(int[] in,int pivo){
        int left = 0;
        int index = 0;
        int right = in.length-1;
        while (index <= right){
            if(in[index] < pivo){
                swap(in,left+1,index);
                left++;
                index++;
            }else if(in[index] > pivo){
                swap(in,right-1,index);
                right--;
            }else {
                index++;
            }
        }
    }
    /**
     * 就是利用上面的第一个问题
     * */
    public static void quickSort1(){

    }
    /**
     * 利用荷兰国旗问题,将1.0版本的<=划分成<和=两个部分,减少多余的比较和交换
     * */
    public static void quickSort2(){

    }
    /**
     * 随机选择支点 O(NlogN)
     * */
    public static void quickSort3(){

    }



}
